pub fn goldbach_conjecture() -> u64 {
    let (prime, is_prime) = init();
    let mut ans = 0;
    let mut time = 0;
    for i in (9..=MAX_N).step_by(2) {
        if !is_prime[i] {
            continue;
        }
        if check(i, &prime) {
            continue;
        }
        ans += i;
        time += 1;
        if time >=2 {
            break;
        }
    }

    println!("{}", ans);
    ans as u64
}

const MAX_N: usize = 1000000;

fn init() -> (Vec<usize>, Vec<bool>) {
    let mut prime = vec![0; MAX_N + 5];
    let mut is_prime = vec![false; MAX_N + 5];
    for i in 2..=MAX_N {
        if !is_prime[i] {
            prime[0] += 1;
            let prime_index = prime[0];
            prime[prime_index] = i;
        }
        for j in 1..=prime[0] {
            if prime[j] * i > MAX_N {
                break;
            }
            is_prime[prime[j] * i] = true;
            if i % prime[j] == 0 {
                break;
            }
        }
    }
    (prime, is_prime)
}

fn sqrt(n: usize) -> usize {
    2 * n * n
}

fn binary_search<F>(func: F, l: usize, r: usize, x: usize) -> bool
where
    F: Fn(usize) -> usize,
{
    let mut l = l;
    let mut r = r;
    while l <= r {
        let mid = (l + r) / 2;
        if func(mid) == x {
            return true;
        }
        if func(mid) < x {
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    false
}

fn check(n: usize, prime: &Vec<usize>) -> bool {
    for j in 1..=prime[0] {
        if prime[j] >= n {
            break;
        }
        if binary_search(sqrt, 1, n - prime[j], n - prime[j]) {
            return true;
        }
    }
    false
}
